{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Climbing Stairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: climbStairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #爬楼梯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>假设你正在爬楼梯。需要 <code>n</code>&nbsp;阶你才能到达楼顶。</p>\n",
    "\n",
    "<p>每次你可以爬 <code>1</code> 或 <code>2</code> 个台阶。你有多少种不同的方法可以爬到楼顶呢？</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>有两种方法可以爬到楼顶。\n",
    "1. 1 阶 + 1 阶\n",
    "2. 2 阶</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>有三种方法可以爬到楼顶。\n",
    "1. 1 阶 + 1 阶 + 1 阶\n",
    "2. 1 阶 + 2 阶\n",
    "3. 2 阶 + 1 阶\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 45</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [climbing-stairs](https://leetcode.cn/problems/climbing-stairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [climbing-stairs](https://leetcode.cn/problems/climbing-stairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2', '3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dp = [0] + [1] + [2] + [0] * (n - 2)\n",
    "        for i in range(3, n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: 'int') -> 'int':\n",
    "        \n",
    "        #使用动态规划\n",
    "        dp = [0 for i in range(n)]\n",
    "        \n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        dp[0], dp[1] = 1, 2\n",
    "        \n",
    "        for i in range(2, n):\n",
    "            dp[i] = dp[i - 2] + dp[i - 1]\n",
    "            \n",
    "        return dp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n < 3:\n",
    "            return n\n",
    "        a, b = 1, 2\n",
    "        for i in range(3, n + 1):\n",
    "            a, b = b, a + b\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(10**8)\n",
    "    def climbStairs(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 2\n",
    "        else:\n",
    "            return self.climbStairs(n - 1) + self.climbStairs(n - 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef calculate_c(self, m, n):\n",
    "\t\t\"\"\"\n",
    "\t\tC(m, n)\n",
    "\t\t:param m: base\n",
    "\t\t:param n: num\n",
    "\t\t:return:\n",
    "\t\t\"\"\"\n",
    "\n",
    "\t\tif n > m // 2:\n",
    "\t\t\tn = m - n\n",
    "\t\t\t\n",
    "\t\tif n == 0:\n",
    "\t\t\treturn 1\n",
    "\n",
    "\t\ta = m\n",
    "\t\tb = n\n",
    "\t\tfor i in range(1, n):\n",
    "\t\t\ta *= m - i\n",
    "\t\t\tb *= n - i\n",
    "\n",
    "\t\treturn int(a / b)\n",
    "\n",
    "\tdef climbStairs(self, n):\n",
    "\t\t\"\"\"\n",
    "\t\t:type n: int\n",
    "\t\t:rtype: int\n",
    "\t\t\"\"\"\n",
    "\t\tresult = 1\n",
    "\t\tfor i in range(1, n // 2 + 1):\n",
    "\t\t\tresult += self.calculate_c(n - i, i)\n",
    "\t\treturn result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        # if n <= 2:\n",
    "        #     return n\n",
    "        # else:\n",
    "        #     temp = 1\n",
    "        #     i = 2\n",
    "        #     ans = 2\n",
    "        #     while i < n:\n",
    "        #         temp, ans = ans, temp + ans\n",
    "        #         i += 1\n",
    "        # return ans \n",
    "        \n",
    "        \n",
    "        fibs = [0, 1]\n",
    "        i = 2\n",
    "        while i <= n + 1:\n",
    "            fibs.append(fibs[i - 1] + fibs[i - 2])\n",
    "            i += 1\n",
    "        return fibs[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n<=0:\n",
    "            return 0\n",
    "        elif n==1:\n",
    "            return 1\n",
    "        elif n==2:\n",
    "            return 2\n",
    "        temp=[0]*n\n",
    "        temp[0]=1\n",
    "        temp[1]=2\n",
    "        for i in range(2,n):\n",
    "            temp[i]=temp[i-1]+temp[i-2]\n",
    "        return temp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.l = []\n",
    "\n",
    "    def climbStairs(self, n):\n",
    "        # 动态规划\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if n<=0:\n",
    "            return 0\n",
    "        if n<=2:\n",
    "            return n\n",
    "        if n>=3:\n",
    "            self.l=[0,1,2]\n",
    "            for i in range(3,n+1):\n",
    "                self.l.append(self.l[i-1]+self.l[i-2])\n",
    "            return self.l[n]\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if(n==1):\n",
    "            return 1;\n",
    "        if(n==2):\n",
    "            return 2;\n",
    "        step=[1,2];\n",
    "        for i in range(2,n+1):\n",
    "            print(i);\n",
    "            step.append(0);\n",
    "            for j in range(0,i):\n",
    "                print(j);\n",
    "                if(j+2>=i):\n",
    "                    step[i]=step[i]+step[j];\n",
    "        return step[n-1];\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: 'int') -> 'int':\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = []\n",
    "        dp.append(1)\n",
    "        dp.append(2)\n",
    "        for i in range(2, n):\n",
    "            dp.append(dp[i-1] + dp[i-2])\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n):\n",
    "        a = b = 1\n",
    "        for _ in range(n):\n",
    "            a, b = b, a + b\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        if n == 0:\n",
    "            ans = 0\n",
    "        elif n == 1:\n",
    "            ans = 1\n",
    "        elif n == 2:\n",
    "            ans = 2\n",
    "        else: \n",
    "            ans_1 = 2\n",
    "            ans_2 = 1\n",
    "            i = 3\n",
    "            while i <= n:\n",
    "                ans = ans_1 + ans_2\n",
    "                ans_2 = ans_1\n",
    "                ans_1 = ans\n",
    "                i = i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        f = [1, 2]\n",
    "        for i in range(2, n):\n",
    "            f.append(f[i-1] + f[i-2])\n",
    "        return f[n-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        One=[1,2]\n",
    "        for i in range(2,n):\n",
    "            One.append(One[i-1]+One[i-2])\n",
    "        return One[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        stepList = [1, 1 , 2]\n",
    "        i = 3\n",
    "        while i <= n:\n",
    "            stepList.append(stepList[i-1]+stepList[i-2])\n",
    "            i += 1\n",
    "        return stepList[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        if n==1:return 1\n",
    "        lst=[1,2]\n",
    "        for i in range(n-2):\n",
    "            lst.append(lst[-1]+lst[-2])\n",
    "        return lst[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        f=[0,1]\n",
    "        for i in range(2,n+2):\n",
    "            f.append(f[i-1]+f[i-2])\n",
    "        return f[n+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        # dp = [0 for i in range(n)]\n",
    "        # dp[0] = 1\n",
    "        # dp[1] = 2\n",
    "\n",
    "        # for i in range(2, n):\n",
    "        #     dp[i] = dp[i-1] + dp[i-2]\n",
    "        # return dp[n-1]\n",
    "\n",
    "        p = 1\n",
    "        q = 2\n",
    "        for i in range(2, n):\n",
    "            temp = q\n",
    "            q = p+q\n",
    "            p = temp\n",
    "        return q\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        if n==1:return 1\n",
    "        if n==2:return 2\n",
    "        return self.climbStairs(n-1)+self.climbStairs(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        a=[-1 for i in range(50000)]\n",
    "        a[1]=1\n",
    "        a[2]=2\n",
    "        for i in range(3,n+1):\n",
    "            a[i]=a[i-1]+a[i-2]\n",
    "        return a[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        f = [0] * 100010\n",
    "        f[0] = 1\n",
    "        f[1] = 2\n",
    "        for i in range(2, n):\n",
    "            f[i] = f[i - 1] + f[i - 2]\n",
    "        \n",
    "        return f[n - 1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 2\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0], dp[1] = 1, 2\n",
    "        for i in range(2, n):\n",
    "            dp[i] = dp[i-1] + dp[i-2]\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    d = [-1] * 123;  # 长度为123的列表，用来缓存结果\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        if self.d[n] != -1:  # climbStairs(n)已经计算过了，不用再次计算，直接返回\n",
    "            return self.d[n]\n",
    "\n",
    "        #print('climbStairs', n)\n",
    "        if n <= 2:\n",
    "            return n\n",
    "        else:\n",
    "            a = 1\n",
    "            b = 2\n",
    "            for i in range(n - 2):\n",
    "                c = a + b\n",
    "                a = b\n",
    "                b = c \n",
    "            return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 2\n",
    "        a = 1\n",
    "        b = 2\n",
    "        for i in range(3, n+1):\n",
    "            dp = a + b\n",
    "            a, b = b, dp\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#动态规划\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        p,q,r=0,0,1\n",
    "        i = 0\n",
    "        while i < n :\n",
    "            p = q\n",
    "            q = r\n",
    "            r = p+q\n",
    "            i +=1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def fib(self, n):\n",
    "        if n < 2:\n",
    "            return 1\n",
    "        return self.fib(n-1) + self.fib(n-2)\n",
    "\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        return self.fib(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        temp_1, temp_2 = 1, 1\n",
    "        for i in range(2, n + 1):\n",
    "            temp_1, temp_2 = temp_2+temp_1, temp_1\n",
    "        return temp_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        if n==1:return 1\n",
    "        if n==2:return 2\n",
    "        if n==3:return 3\n",
    "        else:\n",
    "            mid=int(n/2)\n",
    "            return self.climbStairs(mid)*self.climbStairs(n-mid)+self.climbStairs(mid-1)*self.climbStairs(n-mid-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        pre2, pre1 = 0, 0\n",
    "        res = 1\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            pre2 = pre1\n",
    "            pre1 = res\n",
    "            res = pre2 + pre1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def climbStairs(self, n: int) -> int:\n",
    "        a = 1\n",
    "        b = 1\n",
    "        for i in range(n - 1):\n",
    "            a, b = b, a + b #不能分开写，否则b的值往后推了一个循环\n",
    "        return b"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
